The invention is in the field of information processing. Specifically, the invention relates to conversion from residue number system (RNS) representations of data to mixed base number system representations of data and to extending the base of RNS numbers.
The RNS has received considerable attention in recent times as an effective tool for performing single step, parallel computation of sums, differences, and products. A system employing the RNS may be used for high speed, real time, parallel processing of data.
A difficulty associated with actually achieving fast computation with the RNS is that a RNS representation of a number does not provide explicit sign and magnitude information. The lack of explicit sign and magnitude information hinders overflow detection and rescaling. The capability to detect overflow is a fundamental requirement of any general purpose computer. A slow overflow detection system slows the speed of the entire computational process.
Residue Arithmetic and Its Application to Computer Technology, N.S. Szabo and R.I. Tanaka, (McGraw Hill, New York, 1967), "Residue Arithmetic: A Tutorial with Examples," F.J. Taylor Computer Vol. 17, No. 5, pp. 50-62 (May 1984), and U.S. Pat. No. 4,797,843 issued to Falk et al on Jan. 10, 1989, all incorporated by reference, provide general background information on the RNS and the mixed base number system.
Optical information processors which are ideally suited to perform the parallel computations required in RNS arithmetic are currently under development. There are fundamental differences between optical processors based on optical circuits in which the information carriers are photons and electronic processors based on electronic circuits in which the information carriers are electrons. In optical circuits the photon carriers do not interact with one another, while in electronic circuits the electron carriers do interact with one another. This fact means that in optical circuits interconnect possibilities exist that do not exist with electronic circuits. In particular, optical circuits allow parallel architectures which perform arithmetic and logical operations in completely parallel, single step processes. Since the speed of optical devices is essentially limited to the time it takes for a photon to transit a device, no faster computation time is possible.
Co-pending application 07/414,475, filed Sep. 29, 1989 entitled "Residue Addition Overflow Detection Processor" by T.L. Houk filed concurrently herewith and incorporated herein by reference, discloses a high speed RNS addition overflow detection processor. The residue addition overflow detection processor disclosed in this copending application requires a high speed base extension circuit and a high speed residue to mixed base converter. This application describes a pipelined residue to mixed base converter and base extension processor suitable for use in the residue addition overflow detection processor cited above.
Co-pending application 07/414,474, filed Sep. 29, 1989 entitled "Parallel Residue to Mixed Base Converter" by R.A. Falk also discloses a residue to mixed base converter suitable for use in the residue addition overflow detection processor cited above. The mixed base converters of the "Parallel Residue to Mixed Base Converter" copending application and the instant application are complementary. The mixed base converter of the "Parallel Residue to Mixed Base Converter" copending application performs conversion in a single step; however, it requires more hardware than the instant invention. The instant invention requires less hardware than the converter of the "Parallel Residue to Mixed Base Converter" co-pending application, although the instant invention requires several processing steps. Accordingly, the instant invention would be employed where hardware minimization is a major concern, whereas the converter of the "Parallel Residue to Mixed Base Converter" co-pending application could be employed where minimization of operational time is paramount.
U.S. Pat. No. 4,752,904 issued to Paul, No. 4,709,345 issued to Vu, No. 4,528,641 issued to Burrows, and No. 4,281,391 issued to Huang disclose residue to mixed base converters which use ROMs (read only memory) and latches, adders, or complex processors to implement the conversion process. The inventions disclosed in these patents require complex hardware, and are thus unsuitable for many applications.
Accordingly, there is a need for a simple and high speed base extension processor and for a residue to mixed base converter which requires a minimum of complex hardware.